940. Majority
Element
Given an array of size n, find the majority element. The
majority element is the element that appears more than 
times.
Input. The first line contains number n (1 ≤ n ≤
100). The second line contains n
positive integers.
Output. If the array contains
majority element, then print it. Otherwise print -1.
|
Sample
input 1 |
Sample
output 1 |
|
7 3 3 5 4 2
3 3 |
3 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
4 2 3 2 3 |
-1 |
SOLUTION
stack
Algorithm analysis
Let x be the majority element. We start processing the input numbers. Each
number equal to x we shall push
onto the stack. When a number not equal to x
is received, we shall pop one number from the stack. Then
at the end of processing the data, the top of the stack will contain the
majority element.
Initially clear the stack.
When processing the next element a:
·
If stack is empty, then push(a);
·
If the top of the stack contains number a, then push(a);
·
If the top of the stack contains number other than a, then pop();
If at the end of
processing all the numbers in array, the top of the stack contains some number x (if stack is empty, then there is no majority element), then it should be checked
if it is a majority element. To do this, count how many times the number x appears in the original array. If x appears more than times, then the answer
is affirmative.
At any time stack contains
only one element (possibly multiple times), so let’s simulate the stack with
two variables:
·
maj – number in the stack;
·
cnt – number of times the
number maj appears in the stack;
Example
Consider the first sample.
At the end of
the algorithm the stack contains 3. Let's check if it is a majority element. To do this, we need to count
how many times the number 3 appears in the original array. The number 3 appears
4 times in the array of length
n = 7. Since 4 > 
, the number 3 is a majority element.
Algorithm realization
Store the input sequence
in array m.
int m[110];
Declare variables maj and cnt to simulate the
stack:
·
maj is the number in the
stack;
·
cnt is the number of times
the number maj is present in the
stack;
int maj, cnt;
Read the input data.
scanf("%d",&n);
for(i = 0; i < n; i++)
scanf("%d",&m[i]);
Initially set the stack to be empty.
maj = 0; cnt = 0;
Process the input numbers. Simulate the stack.
for(int i = 0; i < n; i++)
{
If stack is empty (cnt = 0), push
m[i] into it.
if (cnt == 0)
{maj = m[i]; cnt++;}
If the current element m[i] matches
the top of the stack maj, then push
m[i] onto the stack.
else if (m[i] == maj) cnt++;
Otherwise pop element from the stack.
else cnt--;
}
In the variable cnt count how
many times the number maj appears in the
array m.
cnt = 0;
for(int i = 0; i < n; i++)
if (m[i] ==
maj) cnt++;
If cnt > , then the majority element exists. Otherwise it does not (res will be assigned -1).
if(2 * cnt > n) res = maj; else
res = -1;
Print the answer.
printf("%d\n",res);
Java realization
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m[] = new int[n];
for(int i = 0; i < n; i++)
m[i] = sc.nextInt();
int maj = 0, cnt = 0;
for(int i = 0; i < n; i++)
{
if (cnt == 0) {maj = m[i]; cnt++;}
else if (m[i] == maj) cnt++;
else cnt--;
}
cnt =
0;
int res;
for(int i = 0; i < n; i++)
if (m[i] == maj) cnt++;
if(2 * cnt > n) res = maj; else res = -1; // cnt
> nums.size() / 2
System.out.println(res);
}
}
Python realization
Read the input data.
n = int(input())
m = list(map(int, input().split()))
Declare variables maj and cnt to simulate the
stack:
·
maj is the number in the
stack;
·
cnt is the number of times
the number maj is present in the
stack;
Initially set the stack to be empty.
maj = 0
cnt = 0
Process the input numbers. Simulate the stack.
for num in m:
If stack is empty (cnt = 0), push
num into it.
if cnt == 0:
maj = num
cnt += 1
If the current element num matches the top of the stack maj, then push num onto the stack.
elif num == maj:
cnt += 1
Otherwise pop element from the stack.
else:
cnt -= 1
In the variable cnt count how
many times the number maj appears in the
list m.
cnt = 0
for num in m:
if num == maj: cnt += 1
If cnt > , then the majority element exists. Otherwise it does not (res will be assigned -1).
if 2 * cnt > n: res = maj
else: res = -1
Print the answer.
print(res)